package com.wp.动态规划;

/**
 * Created by 王萍 on 2017/10/25 0025.
 */
//求数组的最长递减子序列

//dp[i]表示以array[i]为结尾的最长递减子串的长度。
public class 递减子序列 {

    public static void main(String[] args) {
        int[] array = new int[]{1, 5, 5,2, 1, 4, 3, 6, 0};
        String subsequence = getSubsequence(array);
        System.out.println(subsequence);
    }

    private static String getSubsequence(int[] array) {
        StringBuilder builder = new StringBuilder("");
        int[] dp = new int[array.length];
        dp[0] = 1;

        for (int i = 1; i < array.length; i++) {//求dp数组。
            for (int j = 0; j < i; j++) {
                if (array[j] > array[i] && dp[j] > dp[i]-1) {//这里的dp[i]-1是因为dp[i] = dp[j] + 1;所以dp[i]应该减一保持上一个dp[j]的大小。
                    dp[i] = dp[j] + 1;
                }
            }
            if (dp[i] == 0) dp[i] = 1;
        }
        for (int i = 0; i < array.length; i++) {
            System.out.print(dp[i]);
        }
        System.out.println();
        int number = dp[array.length - 1];
        for (int i = array.length - 1; i >= 0; i--) {
            if (dp[i] == number) {
                builder.append(array[i]);
                number--;
            }
        }
        return builder.reverse().toString();
    }
}
